/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 61. 旋转链表
 * <a href="https://leetcode.cn/problems/rotate-list/">...</a>
 * User: DELL
 * Date: 2023-10-19
 * Time: 23:38
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 非空校验
        if (head == null) {
            return null;
        }
        // 求出链表的节点个数
        int size = getSize(head);
        // 将 k 对 size 取模
        k %= size;
        if (k != 0) {
            ListNode temp = head;
            int dif = size - k;
            // 先找到第 dif 个节点
            while (--dif != 0) {
                temp = temp.next;
            }
            // 那么第 dif + 1 个节点就是新的头节点,这里需要记录一下
            ListNode newHead = temp.next;
            // 将第 dif 个节点的 next 域置为 null
            temp.next = null;
            temp = newHead;
            // 遍历到最后一个节点
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = head;
            return newHead;
        }
        return head;
    }

    /**
     * 求出链表的节点个数
     *
     * @param head
     * @return
     */
    private int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }
}